package com.dbh.alg.algorithm.quest;

import com.dbh.alg.algorithm.hot100.ListNode;

public class Leetcode143_重排链表 {

    public void reorderList(ListNode head) {
        if (head == null || head.next  == null) {
            return;
        }
        ListNode midNode = getMid(head);
        ListNode head1 = reverse(midNode);
        merge(head, head1);
    }

    private ListNode getMid(ListNode head) {
        ListNode pre = null;
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            pre = p1;
            p1 = p1.next;
            p2 = p2.next.next;
        }
        pre.next = null;
        return p1;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private void merge(ListNode head, ListNode head1) {
        ListNode p = head;
        ListNode cur = head1;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = p.next;
            p.next = cur;
            cur = next;
            if (p.next.next != null) {
                p = p.next.next;
            } else {
                p = p.next;
            }
        }
    }
}
